package ljl.alg.hot100;

import commons.TreeNode;

import java.util.LinkedList;

public class _617_merge_binary_tree {
    
    /*
     * 本来想混的不小心做出来了，纯属意外
     *
     * 我这个解法不能说错，但是有点煞笔
     *
     * */
    public TreeNode mergeTrees(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return null;
        int leftVal = left == null ? 0 : left.val;
        int rightVal = right == null ? 0 : right.val;
        TreeNode res = new TreeNode(leftVal + rightVal);
        
        res.left = mergeTrees(safeGet(left, true), safeGet(right, true));
        res.right = mergeTrees(safeGet(left, false), safeGet(right, false));
        
        return res;
    }
    
    TreeNode safeGet(TreeNode node, boolean left) {
        return node == null ? null : left ? node.left : node.right;
    }
    
    public TreeNode mergeTrees_v2(TreeNode left, TreeNode right) {
        if (left == null) return right;
        if (right == null) return left;
        TreeNode root = new TreeNode(left.val + right.val);
        root.left = mergeTrees_v2(left.left, right.left);
        root.right = mergeTrees_v2(left.right, right.right);
        return root;
    }
    
    /**
     * 用到了三个队列，比较繁琐
     * 我把原始 tree 修改了，本来它就有些节点指向原始节点，有些节点是新节点，装啥呢？
     *
     * 可以看到这个解法非常的傻屄，非常的繁琐
     * 还是使用递归优雅！
     * 能用递归就用递归！
     *
     * 不得不说太恶心了
     */
    public TreeNode mergeTrees_iterate(TreeNode left, TreeNode right) {
        if (left == null) return right;
        if (right == null) return left;
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<TreeNode> leftQueue = new LinkedList<>();
        LinkedList<TreeNode> rightQueue = new LinkedList<>();
        left.val += right.val;
        queue.offer(left);
        leftQueue.offer(left);
        rightQueue.offer(right);
        while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
            TreeNode node = queue.poll(), leftNode = leftQueue.poll(), rightNode = rightQueue.poll();
            TreeNode leftLeft = leftNode.left, leftRight = leftNode.right;
            TreeNode rightLeft = rightNode.left, rightRight = rightNode.right;
            if (leftLeft != null && rightLeft != null) {
                node.left.val = leftNode.left.val + rightNode.left.val;
                queue.offer(node.left);
                leftQueue.offer(leftNode.left);
                rightQueue.offer(rightNode.left);
            } else if (leftLeft != null) {
                node.left = leftNode.left;
            } else if (rightLeft != null) {
                node.left = rightNode.left;
            }
            
            if (leftRight != null && rightRight != null) {
                node.right.val = rightNode.right.val + leftNode.right.val;
                queue.offer(node.right);
                leftQueue.offer(leftNode.right);
                rightQueue.offer(rightNode.right);
            } else if (leftRight != null) {
                node.right = leftNode.right;
            } else if(rightRight != null) {
                node.right = rightNode.right;
            }
        }
        return left;
    }
    
}
